package demo2;

/**
 * 剪绳子：贪心算法
 */
public class cutRopeTest2 {
    public static void main(String[] args) {
        System.out.println(cuttingRope(6));
    }

    public static int cuttingRope(int n) {
        if(n < 2) return 0;
        if(n == 2) return 1;  // 1*1
        if(n == 3) return 2;  // 1*2
        //if(n == 4) return 4;  // 2*2

        // 尽可能多的剪成长度为3的,这里是计算一下能减出多少个3
        int timesOf3 = n/3;

        //当绳子最后剩下的长度为4的时候,不能再剪去长度为3的绳子段。
        //此时更好的方法是把绳子剪成长度为2的两段,因为2*2>3*1。
        if(n - timesOf3*3 == 1){  //如果最后只剩一个1
            timesOf3 -= 1;  //就要留下一个3
        }

        //保证剩下的一定是4或者2或者0,计算一下能剪出几个2来(只有2/1/0三种情况)
        int timesOf2 = (n - timesOf3 * 3) / 2;

        //3的多少个3次幂,再乘以2的多少个2次幂,就是贪心选择的最优解
        return (int) (Math.pow(3,timesOf3) * Math.pow(2,timesOf2));
    }
}
